Search Results

Documents authored by Wolter, Diedrich

Document
DOI: 10.4230/LIPIcs.TIME.2020.12
Dynamic Branching in Qualitative Constraint Networks via Counting Local Models

Authors: Michael Sioutis and Diedrich Wolter

Published in: LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)

Abstract
We introduce and evaluate dynamic branching strategies for solving Qualitative Constraint Networks (QCNs), which are networks that are mostly used to represent and reason about spatial and temporal information via the use of simple qualitative relations, e.g., a constraint can be "Task A is scheduled after or during Task C". In qualitative constraint-based reasoning, the state-of-the-art approach to tackle a given QCN consists in employing a backtracking algorithm, where the branching decisions during search are governed by the restrictiveness of the possible relations for a given constraint (e.g., after can be more restrictive than during). In the literature, that restrictiveness is defined a priori by means of static weights that are precomputed and associated with the relations of a given calculus, without any regard to the particulars of a given network instance of that calculus, such as its structure. In this paper, we address this limitation by proposing heuristics that dynamically associate a weight with a relation, based on the count of local models (or local scenarios) that the relation is involved with in a given QCN; these models are local in that they focus on triples of variables instead of the entire QCN. Therefore, our approach is adaptive and seeks to make branching decisions that preserve most of the solutions by determining what proportion of local solutions agree with that decision. Experimental results with a random and a structured dataset of QCNs of Interval Algebra show that it is possible to achieve up to 5 times better performance for structured instances, whilst maintaining non-negligible gains of around 20% for random ones.
Cite as

Michael Sioutis and Diedrich Wolter. Dynamic Branching in Qualitative Constraint Networks via Counting Local Models. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sioutis_et_al:LIPIcs.TIME.2020.12,
  author =	{Sioutis, Michael and Wolter, Diedrich},
  title =	{{Dynamic Branching in Qualitative Constraint Networks via Counting Local Models}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.12},
  URN =		{urn:nbn:de:0030-drops-129802},
  doi =		{10.4230/LIPIcs.TIME.2020.12},
  annote =	{Keywords: Qualitative constraints, spatial and temporal reasoning, counting local models, dynamic branching, adaptive algorithm}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.71
Spatial Information Extraction from Text Using Spatio-Ontological Reasoning (Short Paper)

Authors: Madiha Yousaf and Diedrich Wolter

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
This paper is involved with extracting spatial information from text. We seek to geo-reference all spatial entities mentioned in a piece of text. The focus of this paper is to investigate the contribution of spatial and ontological reasoning to spatial interpretation of text. A preliminary study considering descriptions of cities and geographical regions from English Wikipedia suggests that spatial and ontological reasoning can be more effective to resolve ambiguities in text than a classical text understanding pipeline relying on parsing.
Cite as

Madiha Yousaf and Diedrich Wolter. Spatial Information Extraction from Text Using Spatio-Ontological Reasoning (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 71:1-71:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{yousaf_et_al:LIPIcs.GISCIENCE.2018.71,
  author =	{Yousaf, Madiha and Wolter, Diedrich},
  title =	{{Spatial Information Extraction from Text Using Spatio-Ontological Reasoning}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{71:1--71:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.71},
  URN =		{urn:nbn:de:0030-drops-93997},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.71},
  annote =	{Keywords: spatial information extraction, geo-referencing, spatial reasoning}
}
Document
DOI: 10.4230/DagSemProc.08091.12
Qualitative Arrangement Information for Matching

Authors: Diedrich Wolter

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)

Abstract
In the context of a generalized robot localization task we investigate the utility of qualitative arrangement information in recognition tasks. Qualitative information allows us to make certain knowledge explicit, separating it from uncertain information that we are facing in recognition tasks. This can give rise to efficient matching algorithms for recognition tasks. Particularly qualitative ordering information is very helpful: it can adequately capture certain spatial knowledge and leads to efficient polynomial-time matching algorithms.
Cite as

Diedrich Wolter. Qualitative Arrangement Information for Matching. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{wolter:DagSemProc.08091.12,
  author =	{Wolter, Diedrich},
  title =	{{Qualitative Arrangement Information for Matching}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.12},
  URN =		{urn:nbn:de:0030-drops-16103},
  doi =		{10.4230/DagSemProc.08091.12},
  annote =	{Keywords: Matching, qualitative spatial reasoning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact